package 牛客网在线编程题库;

import java.util.Stack;

/**
 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 * 示例1
 * 输入
 * 复制
 * "["
 * 返回值
 * 复制
 * false
 * 示例2
 * 输入
 * 复制
 * "[]"
 * 返回值
 * 复制
 * true
 */

public class _括号序列 {
    public static void main(String[] args) {
        String s1 = "[";
        String s2 = "[]";
        String s3 = "([)]";
        boolean b = isValid1(s3);
        System.out.println(b);
    }

    public static boolean isValid1(String s) {
        // 定义符号栈
        Stack<Character> stack = new Stack<>();
        // 遍历字符串
        for (int i = 0 ; i < s.length() ; i++) {
            // 取出当前字符
            char c = s.charAt(i);
            // 左括号直接压栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // 如果为右小括号
            else if (c == ')') {
                // 如果此时栈为空
                if (stack.isEmpty()) {
                    // 直接返回
                    return false;
                }
                // 看一眼栈顶元素(不取出)
                char top = stack.peek();
                // 若栈顶不是左括号
                if (top != '(') {
                    // 直接返回
                    return false;
                }
                // 如果是左括号，弹出
                stack.pop();
            }
            // 如果为右中括号
            else if (c == ']') {
                if (stack.isEmpty()) {
                    // 直接返回
                    return false;
                }
                char top = stack.peek();
                // 若栈顶不是左括号
                if (top != '[') {
                    // 直接返回
                    return false;
                }
                // 如果是左括号，弹出
                stack.pop();
            }
            // 如果为右大括号
            else if (c == '}') {
                if (stack.isEmpty()) {
                    // 直接返回
                    return false;
                }
                char top = stack.peek();
                // 若栈顶不是左括号
                if (top != '{') {
                    // 直接返回
                    return false;
                }
                // 如果是左括号，弹出
                stack.pop();
            }
        }
        if (stack.size() != 0) {
            return false;
        }
        return true;
    }
}
